/*
 ============================================================================
 Name        : leftistheap.c
 Author      : Jfhu
 Version     :
 Copyright   : Your copyright notice
 Description : Leftist heap in C, Ansi-style
 ============================================================================
 */

#include <stdlib.h>
#include <stdio.h>
#include "leftistheap.h"

void initializeitem(pItem i)
{
	i->leftChild = i->rightChild = NULL;
	i->rank = 1;
}

void freeitem(pItem i)
{
	if (i != NULL) {
		free(i);
		i = NULL;
	}
}

void initializeheap(pHeap h)
{
	h->root = NULL;
}

pItem findmin(pHeap h)
{
	if (h == NULL)
		return NULL;

	return h->root;
}

pHeap meld(pHeap h1, pHeap h2)
{
	if (h1 == NULL || h1->root == NULL)
		return h2;

	if (h2 == NULL || h2->root == NULL)
		return h1;

	h1->root = mesh(h1->root, h2->root);
	return h1;
}

pItem mesh(pItem i1, pItem i2)
{
	pItem temp;
	if (i1->value > i2->value) {
		temp = i1;
		i1 = i2;
		i2 = temp;
	}

	if (i1->rightChild == NULL) {
		i1->rightChild = i2;
	} else {
		i1->rightChild = mesh(i1->rightChild, i2);
	}

	if (i1->leftChild == NULL || i1->leftChild->rank < i1->rightChild->rank) {
		temp = i1->leftChild;
		i1->leftChild = i1->rightChild;
		i1->rightChild = temp;
	}

	if (i1->rightChild == NULL) {
		i1->rank = 1;
	} else {
		i1->rank = i1->rightChild->rank + 1;
	}
	return i1;
}

void insert(pItem i, pHeap h)
{
	if (i == NULL)
		return;
	if (h->root == NULL) {
		h->root = i;
		return;
	}
	h->root = mesh(i, h->root);
}

pItem deletemin(pHeap h)
{
	pItem t = h->root;

	h->root = mesh(t->leftChild, t->rightChild);

	return t;
}

void listmin(pList l, int x, pItem i)
{
	pListnode n;
	if (i == NULL || i->value > x)
		return;

	n = (pListnode)malloc(sizeof(listnode));
	initializelistnode(n);

	n->value = i->value;
	append(n, l);

	listmin(l, x, i->leftChild);
	listmin(l, x, i->rightChild);
}

pHeap heapify(pHeaplist q)
{
	int i;
	if (q == NULL) {
		printf("leftistheap:heapify: The input heap list is NULL");
		return NULL;
	}
	i = 0;
	while (q->size > 1) {
		pHeap h1 = pop(q);
		pHeap h2 = pop(q);
		h1 = meld(h1, h2);
		printf("Heap after %d melding\n", ++i);
		printfHeap(h1);
		push_back(h1, q);
	}

	if (q->size == 0 || q->head == NULL) {
		printf("leftistheap:heapify: The input list is empty\n");
		return NULL;
	}

	return pop(q);
}

pHeap makeheap(int *arr, int n)
{
	heaplist hl;
	int i;

	initializeheaplist(&hl);
	for (i = 0; i < n; i++) {
		pHeap h = (pHeap)malloc(sizeof(heap));
		initializeheap(h);
		h->root = (pItem)malloc(sizeof(item));
		initializeitem(h->root);
		h->root->value = arr[i];

		push_back(h, &hl);
	}

	return heapify(&hl);
}

void printfHeap(pHeap p)
{
	itemnodelist l;
	if (p == NULL) {
		printf("leftistheap:printfHeap: The input heap is NULL\n");
		return;
	}

	initializeitemnodelist(&l);
	push_backitem(duplicate(p->root), &l);

	while (l.head != NULL) {
		int leftChildValue = -1, rightChildValue = -1;
		pItem i = pop_item(&l);

		if (i->leftChild != NULL) {
			leftChildValue = i->leftChild->value;
			push_backitem(duplicate(i->leftChild), &l);
		}

		if (i->rightChild != NULL) {
			rightChildValue = i->rightChild->value;
			push_backitem(duplicate(i->rightChild), &l);
		}
		printf("value(%d, %d): %d\t rank: %d\n", leftChildValue, rightChildValue, i->value, i->rank);
		freeitem(i);
	}
}

void printfItem(pItem i)
{
	if (i != NULL) {
		printf("value: %d rank: %d\n", i->value, i->rank);
		printfItem(i->leftChild);
		printfItem(i->rightChild);
	}
}

void initializeheaplistnode(pHeaplistnode n)
{
	n->h = NULL;
	n->next = NULL;
}

void initializeheaplistnode1(pHeaplistnode n, pHeap h)
{
	n->h = h;
	n->next = NULL;
}

void freeheaplistnode(pHeaplistnode n)
{
	if (n != NULL) {
		free(n);
		n = NULL;
	}
}

void initializeheaplist(pHeaplist l)
{
	l->head = l->tail = NULL;
	l->size = 0;
}

void push_back(pHeap h, pHeaplist l)
{
	pHeaplistnode n = (pHeaplistnode)malloc(sizeof(heaplistnode));
	initializeheaplistnode1(n, h);

	if (l->head == NULL || l->size == 0) {
		l->head = l->tail = n;
		++l->size;
		return;
	}

	l->tail->next = n;
	l->tail = n;
	++l->size;
}

pHeap pop(pHeaplist l)
{
	pHeaplistnode t;
	pHeap h;
	if (l == NULL) {
		printf("heaplist:pop: the input list is NULL\n");
		return NULL;
	}
	t = l->head;

	if (t == NULL || l->size == 0) {
		printf("heaplist:pop: the input list is empty\n");
		return NULL;
	}
	h = t->h;
	l->head = l->head->next;
	--l->size;
	freeheaplistnode(t);
	return h;
}

pItem duplicate(const pItem i)
{
	pItem t;
	if (i == NULL) {
		printf("leftistheap:duplicate: The input item is NULL\n");
		return NULL;
	}

	t = (pItem)malloc(sizeof(item));
	t->leftChild = i->leftChild;
	t->rank = i->rank;
	t->rightChild = i->rightChild;
	t->value = i->value;

	return t;
}

void push_backitem(pItem i, pItemnodelist l)
{
	pItemnode n;
	if (l == NULL) {
		printf("leftistheap:push_backitem: The input item list is NULL\n");
		return;
	}
	n = (pItemnode)malloc(sizeof(itemnode));
	initializeitemnode1(n, i);

	if (l-> head == NULL) {
		l->head = l->tail = n;
		return;
	}

	l->tail->next = n;
	l->tail = n;
}

pItem pop_item(pItemnodelist l)
{
	pItemnode n;
	pItem i;
	if (l == NULL) {
		printf("leftistheap:pop_item: The input item list is NULL\n");
		return NULL;
	}

	if (l->head == NULL) {
		return NULL;
	}

	n = l->head;
	i = n->i;

	l->head = l->head->next;
	freeitemnode(n);

	return i;
}

void initializeitemnodelist(pItemnodelist l)
{
	l->head = l->tail = NULL;
}

void initializeitemnode(pItemnode n)
{
	n->i = NULL;
	n->next = NULL;
}

void initializeitemnode1(pItemnode n, pItem i)
{
	n->i = i;
	n->next = NULL;
}

void freeitemnode(pItemnode n)
{
	if (n != NULL) {
		free(n);
		n = NULL;
	}
}

